We derive a static potential for a heavy quark-antiquark pair propagating in Minkowski time at finite temperature, by defining a suitable gauge-invariant Green's function and computing it to first non-trivial order in Hard Thermal Loop resummed perturbation theory. The resulting Debye-screened potential could be used in models that attempt to describe the ``melting'' of heavy quarkonium at high temperatures. We show, in particular, that the potential develops an imaginary part, implying that thermal effects generate a finite width for the quarkonium peak in the dilepton production rate. For quarkonium with a very heavy constituent mass M, the width can be ignored for T \lsim g^2 M/12\pi, where g^2 is the strong gauge coupling; for a physical case like bottomonium, it could become important at temperatures as low as 250 MeV. Finally, we point out that the physics related to the finite width originates from the Landau-damping of low-frequency gauge fields, and could be studied non-perturbatively by making use of the classical approximation.